import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-09-15
 * Time: 17:18
 */
public class Sort {
    //交换数组中的两个数
    private static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //快速排序
    public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }
    //快速排序的核心操作
    private static void quick(int[] arr,int i,int j) {
        //当子序列长度小于5时，递归结束，进行插入排序
        if (j - i + 1<= 5) {
            insertSort(arr,i,j);
            return;
        }

        //使用三数取中法
        selectPivotByMedianOfThree(arr,i,j);
        int k = find(arr,i,j);

        //处理左子序列
        quick(arr,i,k-1);

        //处理右子序列
        quick(arr,k+1,j);
    }
    //找基准值的下标
    private static int find(int[] arr,int i,int j) {
        //基准值下标
        int k = i;
        //基准值
        int pivot = arr[k];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,k,i);
        return i;
    }

    //快速排序专用插入排序
    private static void insertSort(int[] arr,int left,int right) {
        for (int i = left + 1; i <= right; i++) {
            int j = i - 1;
            int tmp = arr[i];
            for (; j >= left; j--) {
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }

    //三数取中法
    private static void selectPivotByMedianOfThree(int[] arr,int left,int right) {
        //中间元素
        int mid = (right + left)/2;
        if (arr[left] < arr[right]) {
            // 情况1：左 < 右
            if (arr[mid] < arr[left]) {
                // 中 < 左 < 右 → 左是中值，不用动
                return;
            } else if (arr[mid] > arr[right]) {
                // 左 < 右 < 中 → 右是中值，交换左和右
                swap(arr, left, right);
            } else {
                // 左 < 中 < 右 → 中是中值，交换左和中
                swap(arr, left, mid);
            }
        } else {
            // 情况2：左 >= 右
            if (arr[mid] < arr[right]) {
                // 中 < 右 <= 左 → 右是中值，交换左和右
                swap(arr, left, right);
            } else if (arr[mid] > arr[left]) {
                // 右 <= 左 < 中 → 左是中值，不用动
                return;
            } else {
                // 右 <= 中 <= 左 → 中是中值，交换左和中
                swap(arr, left, mid);
            }
        }
    }




    //找基准值的下标_挖坑法
    private static int find_Dig(int[] arr,int i,int j) {
        //基准值
        int pivot = arr[i];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            arr[i] = arr[j];
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        return i;
    }

    //找基准值的下标_双指针法
    private static int find_TwoPointers(int[] arr,int i,int j) {
        //遍历指针
        int cur = i + 1;
        //指向小于基准值的序列的边界
        int prev = i;
        //基准值
        int pivot = arr[i];

        while (cur <= j) {
            //当遍历到的元素小于基准值时
            if (arr[cur] < pivot) {
                //小于基准值的序列边界扩大
                prev++;
                //当边界的元素和遍历元素是同一个时，不交换
                if (prev != cur) {
                    swap(arr,prev,cur);
                }
            }
            cur++;
        }
        swap(arr,prev,i);
        return prev;
    }

    //快速排序_非递归实现
    public static void quickSortNor(int[] arr) {
        quick(arr,0,arr.length-1);
    }
    //核心操作
    private static void quickNor(int[] arr,int start,int end) {
       Stack<Integer> stack = new Stack<>();

        //第一层划分基准值的位置
        int pivot = find(arr,start,end);

        //确保左子序列长度大于1
        if (pivot > start + 1) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        //确保右子序列长度大于1
        if (pivot < end  - 1) {
            stack.push(pivot + 1);
            stack.push(end);
        }

        while (!stack.empty()) {
            //取出栈储存的子序列
            end = stack.pop();
            start = stack.pop();

            //接着划分
            pivot = find(arr,start,end);

            //确保左子序列长度大于1
            if (pivot > start + 1) {
                stack.push(start);
                stack.push(pivot - 1);
            }
            //确保右子序列长度大于1
            if (pivot < end  - 1) {
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }
}
